//给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。 
//
// 返回被除数 dividend 除以除数 divisor 得到的商。 
//
// 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2 
//
// 
//
// 示例 1: 
//
// 输入: dividend = 10, divisor = 3
//输出: 3
//解释: 10/3 = truncate(3.33333..) = truncate(3) = 3 
//
// 示例 2: 
//
// 输入: dividend = 7, divisor = -3
//输出: -2
//解释: 7/-3 = truncate(-2.33333..) = -2 
//
// 
//
// 提示： 
//
// 
// 被除数和除数均为 32 位有符号整数。 
// 除数不为 0。 
// 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。 
// 
// Related Topics 数学 二分查找 
// 👍 515 👎 0


import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    //这里考察了位运算 1<<n 表示把1扩大2的n次方倍
    //关于位运算 在算法中使用比较少 但是也要要求掌握 它是以二进制为基础的
    //考虑到可能出现溢出 所以进行类型转换
    public int divide(int dividend, int divisor) {
        boolean judgment=false;
        if(dividend>0&&divisor<0||dividend<0&&divisor>0)
            judgment=true;
        List<Long> exps=new ArrayList<>();
       long a=(long)dividend;
       if(dividend<0)
           a=-a;
       long b=(long)divisor;
       if(b<0)
           b=-b;
        long result=0;

        for(long i = b;i <= a;i = i + i){//每次以两倍关系存储
            exps.add(i);
        }
        for(int i=exps.size() - 1; i >= 0; i--){
            if(a>=exps.get(i)){
                a=a-exps.get(i);
                result+=(long)1<<i;//位运算 取出每个exps.get(i)扩大a的倍数
            }
        }
        if (judgment)
            result=-result;
        if(result>Integer.MAX_VALUE||result<Integer.MIN_VALUE)
            return Integer.MAX_VALUE;
        return (int)result;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
